import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 28
 * Time: 22:21
 */
//牛客 判断是不是完全二叉树
public class Solution5 {
    //根据官方推荐方法自己写的代码
    public boolean isCompleteTree (TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode node = queue.poll();
        while(node != null) {
            queue.offer(node.left);
            queue.offer(node.right);
            node = queue.poll();
        }
        while (!queue.isEmpty()) {
            node = queue.poll();
            if(node != null) {
                return false;
            }
        }
        return true;
    }

    //官方推荐方法
    public boolean isCompleteTree1 (TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean notComplete = false;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur == null) {
                notComplete = true;
                continue;
            }
            if(notComplete) {
                return false;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }
}
